#include "findpaththread.h"
#include <QQueue>
#include <QHash>
#include <QDebug>
FindpathThread::FindpathThread(QObject *parent)
    : QThread(parent)
{

}

void FindpathThread::init(const QString &type, QHash<QString, QSharedPointer<Node>>* id_nodes, QHash<QString, QList<Edge> > *graph, const QString &src, const QString &dst, QVector<QString> *path, bool *finded, QHash<QString, QHash<QString, QStringList>>*line, int* transfer)
{
    _type = type;
    _id_nodes = id_nodes;
    _graph = graph;
    _src = src;
    _dst = dst;
    _finded = finded;
    _path = path;
    _lines = line;
    _transfer = transfer;
}

void FindpathThread::run()
{
    qDebug() << "开始查找";

    if(_type == "最少站点") bfs();
    if(_type == "最少换乘") lesstransfer();
}

void FindpathThread::bfs()
{
    QQueue<QString> q;
    QHash<QString, bool> visited;
    QHash<QString, QString> parent;
    QVector<QString> path;

    visited[_src] = true;
    q.push_back(_src);
    while(q.size()){
        int k = q.size();
        while(k--){
            QString cur = q.front(); q.pop_front();
            for(auto edge : (*_graph)[cur]){
                QString id;
                if(edge.id1 == cur){
                    id = edge.id2;
                } else {
                    id = edge.id1;
                }
                if(visited.count(id)) continue;
                visited[id] = true;
                parent[id] = cur;
                if(id == _dst) goto Found;
                q.push_back(id);
            }
        }
    }
    *_finded = false;
    *_path = path;
    qDebug() << "没找到";
    return;

Found:
    while(parent.count(_dst)){
        qDebug() << _dst;
        path.push_front(_dst);
        _dst = parent[_dst];
    }
    path.push_front(_src);
    *_finded = true;
    *_path = path;
    findPath(1);
    qDebug() << "找到了";
}

void FindpathThread::lesstransfer()
{
    qDebug() << "最少换乘";
    // 下面得把 站点和路线(简记为state) 绑定,不然不同路线的同一站点可能无法被访问,导致寻路失败
    QQueue<QPair<QPair<QString, QString>, int>> q; // ((站点, 线路), 换乘次数)
    QSet<QPair<QString, QString>> visited;         // 已访问的state
    QHash<QPair<QString, QString>, QPair<QString, QString>> parent; // 父状态

    if (_src == _dst) {
        *_finded = true;
        *_path = {_src};
        *_transfer = 0;
        qDebug() << "找到了，换乘次数：0";
        return;
    }

    // 初始化：起点的所有线路
    for (const auto& edge : (*_graph)[_src]) {
        QPair<QString, QString> state(_src, edge.line);
        q.push_back({state, 0});
        visited.insert(state);
    }

    while (!q.empty()) {
        auto state = q.front().first; // 当前状态
        auto transfers = q.front().second; // 当前换乘次数
        q.pop_front();
        auto station = state.first; // 当前站点
        auto line = state.second; // 当前线路

        // 先处理当前线路,把换乘次数少的push进队列,再处理换乘次数+1的
        // 沿当前线路前进
        for (const auto& next : (*_lines)[line][station]) {
            QPair<QString, QString> next_state(next, line);
            if (visited.contains(next_state)) continue;

            visited.insert(next_state);
            parent[next_state] = state;

            if (next == _dst) {
                // 开始回溯找路:
                QVector<QString> path;
                auto cur = next_state;
                while (parent.contains(cur)) {
                    path.push_front(cur.first);
                    cur = parent[cur];
                }
                path.push_front(_src);
                *_finded = true;
                *_path = path;
                *_transfer = transfers;
                findPath(2);
                qDebug() << "找到了，换乘次数：" << transfers;
                return;
            }
            q.push_back({next_state, transfers});
        }

        // 换乘到其他线路
        for (const auto& edge : (*_graph)[station]) {
            if (edge.line == line) continue;

            QPair<QString, QString> next_state(station, edge.line);
            if (!visited.contains(next_state)) {
                visited.insert(next_state);
                parent[next_state] = state;
                q.push_back({next_state, transfers + 1});
            }
        }
    }

    *_finded = false;
    *_path = QVector<QString>();
    qDebug() << "没找到";
}
